package sword_offer;

public class _04FindNumberIn2DArray {
    public static void main(String[] args) {
        int[][] nums = {
                {1,   4,  7, 11, 15},
                  {2,   5,  8, 12, 19},
                  {3,   6,  9, 16, 22},
                  {10, 13, 14, 17, 24},
                  {18, 21, 23, 26, 30}
                };
        boolean repeatNumber = new _04FindNumberIn2DArray().findNumberIn2DArray(nums, 15);
        System.out.println(repeatNumber);
    }

    public boolean findNumberIn2DArray(int[][] matrix, int target) {
        if (matrix.length == 0)
            return false;
        final int HEIGHT = matrix.length, WIDTH = matrix[0].length;
        int x = 0, y = WIDTH - 1;
        while (x < HEIGHT && y > -1){
            // 制定位置的值和target做比较，移动位置
            if (matrix[x][y] == target){
                return true;
            }else if (matrix[x][y] > target){
                y--;
            }else {
                x++;
            }
        }

        return false;
    }
}
